package Algorithm.erfenchazhao;

/**
 * 二分查找非递归算法
 */
public class BinarySearchNoRecur {
    public static void main(String[] args) {

        //测试
        int[] arr = {1,2,3,4,5,6,7};
        int i = binarySearch(arr, 0);
        if(i !=-1){
            System.out.println(arr[i]);
        }else{
            System.out.println("未找到");
        }
    }

    //非递归的二分查找算法
    /**
     *
     * @param arr 待查找的数组（升序）
     * @param target 需要查找的数
     * @return 返回查找的下标
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {  //说明可以继续查找
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {  //左边去找
                right = mid - 1; //right的下标变化了
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}
